package com.example.demo.leetcode.top100;

import java.util.LinkedList;
import java.util.List;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _56子集
 * @description
 * @date 2023/06/20 17:26
 * <p>
 * ******************************************************
 */
public class _56子集 {

    List<List<Integer>> res = new LinkedList<>();


    public List<List<Integer>> subsets(int[] nums) {

        LinkedList<Integer> trace = new LinkedList<>();
        boolean[] used = new boolean[nums.length];
        backtrack(0, nums, trace, used);


        return res;

    }

    private void backtrack(int i, int[] nums, LinkedList<Integer> trace, boolean[] used) {
        res.add(new LinkedList<>(trace));

        for (int j = i; j < nums.length; j++) {
            int num = nums[j];

            if (used[j]) {
                continue;
            }
            used[j] = true;
            trace.add(num);
            backtrack(j, nums, trace, used);
            used[j] = false;
            trace.removeLast();
        }
    }

    public List<List<Integer>> subsets1(int[] nums) {

        LinkedList<Integer> trace = new LinkedList<>();
        boolean[] used = new boolean[nums.length];
        backtrack1(nums, trace, used);


        return res;

    }

    private void backtrack1(int[] nums, LinkedList<Integer> trace, boolean[] used) {
        if (res.stream().anyMatch(item -> item.containsAll(trace) && item.size() == trace.size())) {
            return;
        }
        res.add(new LinkedList<>(trace));

        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];

            if (used[i]) {
                continue;
            }
            used[i] = true;
            trace.add(num);
            backtrack1(nums, trace, used);
            used[i] = false;
            trace.removeLast();
        }
    }


    public static void main(String[] args) {
        _56子集 s = new _56子集();
        s.subsets(new int[]{1, 2, 3});
    }
}
